/* name: clear
 * author: 5ab
 * created at: 2024-06-13
 */
#include <bits/stdc++.h>
using namespace std;

#define all(x) (x).begin(), (x).end()
#define ssz(x) (int((x).size()))

auto chmax = [](auto& x, auto y) { if (x < y) x = y; };
auto chmin = [](auto& x, auto y) { if (y < x) x = y; };

using ll = long long;
const int N = 1.5e5;

int a[N];

signed main()
{
	freopen("clear.in", "r", stdin);
	freopen("clear.out", "w", stdout);
	
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, m, q;
	
	cin >> n >> m >> q;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	
	deque<int> cs;
	
	int l, r;
	while (q--)
	{
		cin >> l >> r, l--, r--;
		cs.clear();
		ll csm = 0, ans = 0;
		for (int i = l; i <= r; i++)
		{
			if (ssz(cs) >= m)
			{
				csm -= cs.back();
				cs.pop_back();
			}
			while (csm > a[i])
			{
				if (csm - cs.back() < a[i])
				{
					cs.back() -= csm - a[i], csm = a[i];
					break;
				}
				csm -= cs.back();
				cs.pop_back();
			}
			if (csm < a[i])
			{
				cs.push_front(a[i] - csm);
				ans += a[i] - csm, csm = a[i];
			}
			else
				cs.push_front(0);
		}
		cout << ans << "\n";
	}
	
	return 0;
}
// started coding at: 06-13 09:49:19